/**
 * 插入排序
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 * 
 * 工作原理：
 * 1. 将数组分为"已排序"和"未排序"两部分
 * 2. 初始时，已排序部分只包含第一个元素
 * 3. 从未排序部分取出一个元素，插入到已排序部分的正确位置
 * 4. 重复步骤3，直到未排序部分为空
 * 
 * @param {Array} arr - 待排序数组
 * @returns {Array} - 排序后的数组（引用相同）
 */
function insertionSort(arr) {
    // 处理边界情况
    if (arr.length <= 1) {
        return arr;
    }
    
    // 从第二个元素开始遍历（第一个元素默认已排序）
    for (let i = 1; i < arr.length; i++) {
        // 保存当前要插入的元素
        let current = arr[i];
        let j = i - 1;
        
        // 从已排序区间的末尾向前查找插入位置
        // 将大于current的元素向后移动一位
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 找到插入位置，将current插入
        arr[j + 1] = current;
    }
    
    return arr;
}

// 测试函数
function testInsertionSort() {
    let arr = [];
    for (let i = 0; i < 10; i++) {
        arr.push(Math.floor(Math.random() * 100));
    }
    
    console.log("排序前:", arr);
    insertionSort(arr);
    console.log("排序后:", arr);
    
    // 验证排序结果
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            console.log("排序失败!");
            return;
        }
    }
    console.log("排序成功!");
}

// 运行测试
testInsertionSort();